#include <stdio.h>
int Euclid(int a, int b);
int q,x,y;
void extend_Eulid(int a,int b);
int main() {
        int a, b;
        printf("输入两个整数：");
        scanf("%d%d", &a, &b);
        printf("最大公约数为：%d\n",Euclid(a, b));
        extend_Eulid(a,b);
        printf("%d=(%d)*%d+(%d)*%d\n",q,x,a,y,b);
       // printf("%d模%d的逆为：%d\n",a,b,extended_gcd(a,b,0,0));
        return 0;
}


int extended_gcd(int a,int b,int x,int y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int r=extended_gcd(b,a%b,x,y);

    int tmp=x;
    x=y;
    y=tmp-a/b*y;

    return r;
}


void extend_Eulid(int a,int b){
        if(b==0){
                x=1;
                y=0;
                q=a;
        }
        else{
                extend_Eulid(b,a%b);
                int temp=x;
                x=y;
                y=temp-a/b*y;
	}
}


int Euclid(int a, int b) {
        int r, num = 0;
//      printf("gcd(%d,%d)\n", a, b);
        if(a>=0&b>=0){
        while(b != 0) {
                r = a % b;
                a = b;
                b = r;
                num++;
                if(b == 0){
                        num++;
//                      printf("=(%d,%d)\n", a, b); 
//                      printf("=%d\n", a);
                        break;
                }
//              printf("=(%d,%d)\n", a, b);     
        }}
//      printf("一共用了%d次\n", num);
        return a;
}
